<!DOCTYPE html>
<html class="client-nojs vector-feature-night-mode-disabled vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-sticky-header-enabled" lang="en" dir="ltr"><head>
<meta charset="UTF-8">
<title>Sample complexity</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="canonical" href="https://en.wikipedia.org/wiki/Sample_complexity"> <link href="./mw/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/skins.vector.styles.css" rel="stylesheet" type="text/css">
<link href="./mw/user.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link rel="stylesheet" type="text/css" href="./mw/site.styles.css">
<link rel="stylesheet" type="text/css" href="./mw/noscript.css">
<link rel="stylesheet" type="text/css" href="./footer.css">
<link rel="stylesheet" type="text/css" href="./vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Sample_complexity rootpage-Sample_complexity skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading">
<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Sample complexity</span></span>
</h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="en" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr">
<style data-mw-deduplicate="TemplateStyles:r1129693374">
/* start https://en.wikipedia.org/ */
.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}
/* end https://en.wikipedia.org/ */
</style><style data-mw-deduplicate="TemplateStyles:r1246091330">
/* start https://en.wikipedia.org/ */
.mw-parser-output .sidebar{width:22em;float:right;clear:right;margin:0.5em 0 1em 1em;background:var(--background-color-neutral-subtle,#f8f9fa);border:1px solid var(--border-color-base,#a2a9b1);padding:0.2em;text-align:center;line-height:1.4em;font-size:88%;border-collapse:collapse;display:table}body.skin-minerva .mw-parser-output .sidebar{display:table!important;float:right!important;margin:0.5em 0 1em 1em!important}.mw-parser-output .sidebar-subgroup{width:100%;margin:0;border-spacing:0}.mw-parser-output .sidebar-left{float:left;clear:left;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-none{float:none;clear:both;margin:0.5em 1em 1em 0}.mw-parser-output .sidebar-outer-title{padding:0 0.4em 0.2em;font-size:125%;line-height:1.2em;font-weight:bold}.mw-parser-output .sidebar-top-image{padding:0.4em}.mw-parser-output .sidebar-top-caption,.mw-parser-output .sidebar-pretitle-with-top-image,.mw-parser-output .sidebar-caption{padding:0.2em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-pretitle{padding:0.4em 0.4em 0;line-height:1.2em}.mw-parser-output .sidebar-title,.mw-parser-output .sidebar-title-with-pretitle{padding:0.2em 0.8em;font-size:145%;line-height:1.2em}.mw-parser-output .sidebar-title-with-pretitle{padding:0.1em 0.4em}.mw-parser-output .sidebar-image{padding:0.2em 0.4em 0.4em}.mw-parser-output .sidebar-heading{padding:0.1em 0.4em}.mw-parser-output .sidebar-content{padding:0 0.5em 0.4em}.mw-parser-output .sidebar-content-with-subgroup{padding:0.1em 0.4em 0.2em}.mw-parser-output .sidebar-above,.mw-parser-output .sidebar-below{padding:0.3em 0.8em;font-weight:bold}.mw-parser-output .sidebar-collapse .sidebar-above,.mw-parser-output .sidebar-collapse .sidebar-below{border-top:1px solid #aaa;border-bottom:1px solid #aaa}.mw-parser-output .sidebar-navbar{text-align:right;font-size:115%;padding:0 0.4em 0.4em}.mw-parser-output .sidebar-list-title{padding:0 0.4em;text-align:left;font-weight:bold;line-height:1.6em;font-size:105%}.mw-parser-output .sidebar-list-title-c{padding:0 0.4em;text-align:center;margin:0 3.3em}@media(max-width:640px){body.mediawiki .mw-parser-output .sidebar{width:100%!important;clear:both;float:none!important;margin-left:0!important;margin-right:0!important}}body.skin--responsive .mw-parser-output .sidebar a>img{max-width:none!important}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-night .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-list-title,html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle{background:transparent!important}html.skin-theme-clientpref-os .mw-parser-output .sidebar:not(.notheme) .sidebar-title-with-pretitle a{color:var(--color-progressive)!important}}@media print{body.ns-0 .mw-parser-output .sidebar{display:none!important}}
/* end https://en.wikipedia.org/ */
</style><style data-mw-deduplicate="TemplateStyles:r886047488">
/* start https://en.wikipedia.org/ */
.mw-parser-output .nobold{font-weight:normal}
/* end https://en.wikipedia.org/ */
</style><table class="sidebar sidebar-collapse nomobile nowraplinks"><tbody><tr><td class="sidebar-pretitle">Part of a series on</td></tr><tr><th class="sidebar-title-with-pretitle"><a href="Machine_learning" title="Machine learning">Machine learning</a><br>and <a href="Data_mining" title="Data mining">data mining</a></th></tr><tr><td class="sidebar-content">
<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Paradigms</div><div class="sidebar-list-content mw-collapsible-content hlist">
<ul><li><a href="Supervised_learning" title="Supervised learning">Supervised learning</a></li>
<li><a href="Unsupervised_learning" title="Unsupervised learning">Unsupervised learning</a></li>
<li><a href="Semi-supervised_learning" class="mw-redirect" title="Semi-supervised learning">Semi-supervised learning</a></li>
<li><a href="Self-supervised_learning" title="Self-supervised learning">Self-supervised learning</a></li>
<li><a href="Reinforcement_learning" title="Reinforcement learning">Reinforcement learning</a></li>
<li><a href="Meta-learning_(computer_science)" title="Meta-learning (computer science)">Meta-learning</a></li>
<li><a href="Online_machine_learning" title="Online machine learning">Online learning</a></li>
<li><a href="Batch_learning" class="mw-redirect" title="Batch learning">Batch learning</a></li>
<li><a href="Curriculum_learning" title="Curriculum learning">Curriculum learning</a></li>
<li><a href="Rule-based_machine_learning" title="Rule-based machine learning">Rule-based learning</a></li>
<li><a href="Neuro-symbolic_AI" title="Neuro-symbolic AI">Neuro-symbolic AI</a></li>
<li><a href="Neuromorphic_engineering" class="mw-redirect" title="Neuromorphic engineering">Neuromorphic engineering</a></li>
<li><a href="Quantum_machine_learning" title="Quantum machine learning">Quantum machine learning</a></li></ul></div></div></td>
</tr><tr><td class="sidebar-content">
<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Problems</div><div class="sidebar-list-content mw-collapsible-content hlist">
<ul><li><a href="Statistical_classification" title="Statistical classification">Classification</a></li>
<li><a href="Generative_model" title="Generative model">Generative modeling</a></li>
<li><a href="Regression_analysis" title="Regression analysis">Regression</a></li>
<li><a href="Cluster_analysis" title="Cluster analysis">Clustering</a></li>
<li><a href="Dimensionality_reduction" title="Dimensionality reduction">Dimensionality reduction</a></li>
<li><a href="Density_estimation" title="Density estimation">Density estimation</a></li>
<li><a href="Anomaly_detection" title="Anomaly detection">Anomaly detection</a></li>
<li><a href="Data_cleaning" class="mw-redirect" title="Data cleaning">Data cleaning</a></li>
<li><a href="Automated_machine_learning" title="Automated machine learning">AutoML</a></li>
<li><a href="Association_rule_learning" title="Association rule learning">Association rules</a></li>
<li><a href="Semantic_analysis_(machine_learning)" title="Semantic analysis (machine learning)">Semantic analysis</a></li>
<li><a href="Structured_prediction" title="Structured prediction">Structured prediction</a></li>
<li><a href="Feature_engineering" title="Feature engineering">Feature engineering</a></li>
<li><a href="Feature_learning" title="Feature learning">Feature learning</a></li>
<li><a href="Learning_to_rank" title="Learning to rank">Learning to rank</a></li>
<li><a href="Grammar_induction" title="Grammar induction">Grammar induction</a></li>
<li><a href="Ontology_learning" title="Ontology learning">Ontology learning</a></li>
<li><a href="Multimodal_learning" title="Multimodal learning">Multimodal learning</a></li></ul></div></div></td>
</tr><tr><td class="sidebar-content">
<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><div style="display: inline-block; line-height: 1.2em; padding: .1em 0;"><a href="Supervised_learning" title="Supervised learning">Supervised learning</a><br><span class="nobold"><span style="font-size: 85%;">(<b><a href="Statistical_classification" title="Statistical classification">classification</a></b> • <b><a href="Regression_analysis" title="Regression analysis">regression</a></b>)</span></span> </div></div><div class="sidebar-list-content mw-collapsible-content hlist">
<ul><li><a href="Apprenticeship_learning" title="Apprenticeship learning">Apprenticeship learning</a></li>
<li><a href="Decision_tree_learning" title="Decision tree learning">Decision trees</a></li>
<li><a href="Ensemble_learning" title="Ensemble learning">Ensembles</a>
<ul><li><a href="Bootstrap_aggregating" title="Bootstrap aggregating">Bagging</a></li>
<li><a href="Boosting_(machine_learning)" title="Boosting (machine learning)">Boosting</a></li>
<li><a href="Random_forest" title="Random forest">Random forest</a></li></ul></li>
<li><a href="K-nearest_neighbors_algorithm" title="K-nearest neighbors algorithm"><i>k</i>-NN</a></li>
<li><a href="Linear_regression" title="Linear regression">Linear regression</a></li>
<li><a href="Naive_Bayes_classifier" title="Naive Bayes classifier">Naive Bayes</a></li>
<li><a href="Artificial_neural_network" class="mw-redirect" title="Artificial neural network">Artificial neural networks</a></li>
<li><a href="Logistic_regression" title="Logistic regression">Logistic regression</a></li>
<li><a href="Perceptron" title="Perceptron">Perceptron</a></li>
<li><a href="Relevance_vector_machine" title="Relevance vector machine">Relevance vector machine (RVM)</a></li>
<li><a href="Support_vector_machine" title="Support vector machine">Support vector machine (SVM)</a></li></ul></div></div></td>
</tr><tr><td class="sidebar-content">
<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Cluster_analysis" title="Cluster analysis">Clustering</a></div><div class="sidebar-list-content mw-collapsible-content hlist">
<ul><li><a href="BIRCH" title="BIRCH">BIRCH</a></li>
<li><a href="CURE_algorithm" title="CURE algorithm">CURE</a></li>
<li><a href="Hierarchical_clustering" title="Hierarchical clustering">Hierarchical</a></li>
<li><a href="K-means_clustering" title="K-means clustering"><i>k</i>-means</a></li>
<li><a href="Fuzzy_clustering" title="Fuzzy clustering">Fuzzy</a></li>
<li><a href="Expectation%E2%80%93maximization_algorithm" title="Expectation–maximization algorithm">Expectation–maximization (EM)</a></li>
<li><br><a href="DBSCAN" title="DBSCAN">DBSCAN</a></li>
<li><a href="OPTICS_algorithm" title="OPTICS algorithm">OPTICS</a></li>
<li><a href="Mean_shift" title="Mean shift">Mean shift</a></li></ul></div></div></td>
</tr><tr><td class="sidebar-content">
<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Dimensionality_reduction" title="Dimensionality reduction">Dimensionality reduction</a></div><div class="sidebar-list-content mw-collapsible-content hlist">
<ul><li><a href="Factor_analysis" title="Factor analysis">Factor analysis</a></li>
<li><a href="Canonical_correlation" title="Canonical correlation">CCA</a></li>
<li><a href="Independent_component_analysis" title="Independent component analysis">ICA</a></li>
<li><a href="Linear_discriminant_analysis" title="Linear discriminant analysis">LDA</a></li>
<li><a href="Non-negative_matrix_factorization" title="Non-negative matrix factorization">NMF</a></li>
<li><a href="Principal_component_analysis" title="Principal component analysis">PCA</a></li>
<li><a href="Proper_generalized_decomposition" title="Proper generalized decomposition">PGD</a></li>
<li><a href="T-distributed_stochastic_neighbor_embedding" title="T-distributed stochastic neighbor embedding">t-SNE</a></li>
<li><a href="Sparse_dictionary_learning" title="Sparse dictionary learning">SDL</a></li></ul></div></div></td>
</tr><tr><td class="sidebar-content">
<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Structured_prediction" title="Structured prediction">Structured prediction</a></div><div class="sidebar-list-content mw-collapsible-content hlist">
<ul><li><a href="Graphical_model" title="Graphical model">Graphical models</a>
<ul><li><a href="Bayesian_network" title="Bayesian network">Bayes net</a></li>
<li><a href="Conditional_random_field" title="Conditional random field">Conditional random field</a></li>
<li><a href="Hidden_Markov_model" title="Hidden Markov model">Hidden Markov</a></li></ul></li></ul></div></div></td>
</tr><tr><td class="sidebar-content">
<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Anomaly_detection" title="Anomaly detection">Anomaly detection</a></div><div class="sidebar-list-content mw-collapsible-content hlist">
<ul><li><a href="Random_sample_consensus" title="Random sample consensus">RANSAC</a></li>
<li><a href="K-nearest_neighbors_algorithm" title="K-nearest neighbors algorithm"><i>k</i>-NN</a></li>
<li><a href="Local_outlier_factor" title="Local outlier factor">Local outlier factor</a></li>
<li><a href="Isolation_forest" title="Isolation forest">Isolation forest</a></li></ul></div></div></td>
</tr><tr><td class="sidebar-content">
<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Neural_network_(machine_learning)" title="Neural network (machine learning)">Neural networks</a></div><div class="sidebar-list-content mw-collapsible-content hlist">
<ul><li><a href="Autoencoder" title="Autoencoder">Autoencoder</a></li>
<li><a href="Deep_learning" title="Deep learning">Deep learning</a></li>
<li><a href="Feedforward_neural_network" title="Feedforward neural network">Feedforward neural network</a></li>
<li><a href="Recurrent_neural_network" title="Recurrent neural network">Recurrent neural network</a>
<ul><li><a href="Long_short-term_memory" title="Long short-term memory">LSTM</a></li>
<li><a href="Gated_recurrent_unit" title="Gated recurrent unit">GRU</a></li>
<li><a href="Echo_state_network" title="Echo state network">ESN</a></li>
<li><a href="Reservoir_computing" title="Reservoir computing">reservoir computing</a></li></ul></li>
<li><a href="Boltzmann_machine" title="Boltzmann machine">Boltzmann machine</a>
<ul><li><a href="Restricted_Boltzmann_machine" title="Restricted Boltzmann machine">Restricted</a></li></ul></li>
<li><a href="Generative_adversarial_network" title="Generative adversarial network">GAN</a></li>
<li><a href="Diffusion_model" title="Diffusion model">Diffusion model</a></li>
<li><a href="Self-organizing_map" title="Self-organizing map">SOM</a></li>
<li><a href="Convolutional_neural_network" title="Convolutional neural network">Convolutional neural network</a>
<ul><li><a href="U-Net" title="U-Net">U-Net</a></li>
<li><a href="LeNet" title="LeNet">LeNet</a></li>
<li><a href="AlexNet" title="AlexNet">AlexNet</a></li>
<li><a href="DeepDream" title="DeepDream">DeepDream</a></li></ul></li>
<li><a href="Neural_field" title="Neural field">Neural field</a>
<ul><li><a href="Neural_radiance_field" title="Neural radiance field">Neural radiance field</a></li>
<li><a href="Physics-informed_neural_networks" title="Physics-informed neural networks">Physics-informed neural networks</a></li></ul></li>
<li><a href="Transformer_(deep_learning_architecture)" title="Transformer (deep learning architecture)">Transformer</a>
<ul><li><a href="Vision_transformer" title="Vision transformer">Vision</a></li></ul></li>
<li><a href="Mamba_(deep_learning_architecture)" title="Mamba (deep learning architecture)">Mamba</a></li>
<li><a href="Spiking_neural_network" title="Spiking neural network">Spiking neural network</a></li>
<li><a href="Memtransistor" title="Memtransistor">Memtransistor</a></li>
<li><a href="Electrochemical_RAM" title="Electrochemical RAM">Electrochemical RAM</a> (ECRAM)</li></ul></div></div></td>
</tr><tr><td class="sidebar-content">
<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)"><a href="Reinforcement_learning" title="Reinforcement learning">Reinforcement learning</a></div><div class="sidebar-list-content mw-collapsible-content hlist">
<ul><li><a href="Q-learning" title="Q-learning">Q-learning</a></li>
<li><a href="Policy_gradient_method" title="Policy gradient method">Policy gradient</a></li>
<li><a href="State%E2%80%93action%E2%80%93reward%E2%80%93state%E2%80%93action" title="State–action–reward–state–action">SARSA</a></li>
<li><a href="Temporal_difference_learning" title="Temporal difference learning">Temporal difference (TD)</a></li>
<li><a href="Multi-agent_reinforcement_learning" title="Multi-agent reinforcement learning">Multi-agent</a>
<ul><li><a href="Self-play_(reinforcement_learning_technique)" class="mw-redirect" title="Self-play (reinforcement learning technique)">Self-play</a></li></ul></li></ul></div></div></td>
</tr><tr><td class="sidebar-content">
<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Learning with humans</div><div class="sidebar-list-content mw-collapsible-content hlist">
<ul><li><a href="Active_learning_(machine_learning)" title="Active learning (machine learning)">Active learning</a></li>
<li><a href="Crowdsourcing" title="Crowdsourcing">Crowdsourcing</a></li>
<li><a href="Human-in-the-loop" title="Human-in-the-loop">Human-in-the-loop</a></li>
<li><a href="Mechanistic_interpretability" title="Mechanistic interpretability">Mechanistic interpretability</a></li>
<li><a href="Reinforcement_learning_from_human_feedback" title="Reinforcement learning from human feedback">RLHF</a></li></ul></div></div></td>
</tr><tr><td class="sidebar-content">
<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Model diagnostics</div><div class="sidebar-list-content mw-collapsible-content hlist">
<ul><li><a href="Coefficient_of_determination" title="Coefficient of determination">Coefficient of determination</a></li>
<li><a href="Confusion_matrix" title="Confusion matrix">Confusion matrix</a></li>
<li><a href="Learning_curve_(machine_learning)" title="Learning curve (machine learning)">Learning curve</a></li>
<li><a href="Receiver_operating_characteristic" title="Receiver operating characteristic">ROC curve</a></li></ul></div></div></td>
</tr><tr><td class="sidebar-content">
<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Mathematical foundations</div><div class="sidebar-list-content mw-collapsible-content hlist">
<ul><li><a href="Kernel_machines" class="mw-redirect" title="Kernel machines">Kernel machines</a></li>
<li><a href="Bias%E2%80%93variance_tradeoff" title="Bias–variance tradeoff">Bias–variance tradeoff</a></li>
<li><a href="Computational_learning_theory" title="Computational learning theory">Computational learning theory</a></li>
<li><a href="Empirical_risk_minimization" title="Empirical risk minimization">Empirical risk minimization</a></li>
<li><a href="Occam_learning" title="Occam learning">Occam learning</a></li>
<li><a href="Probably_approximately_correct_learning" title="Probably approximately correct learning">PAC learning</a></li>
<li><a href="Statistical_learning_theory" title="Statistical learning theory">Statistical learning</a></li>
<li><a href="Vapnik%E2%80%93Chervonenkis_theory" title="Vapnik–Chervonenkis theory">VC theory</a></li>
<li><a href="Topological_deep_learning" title="Topological deep learning">Topological deep learning</a></li></ul></div></div></td>
</tr><tr><td class="sidebar-content">
<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Journals and conferences</div><div class="sidebar-list-content mw-collapsible-content hlist">
<ul><li><a href="AAAI_Conference_on_Artificial_Intelligence" title="AAAI Conference on Artificial Intelligence">AAAI</a></li>
<li><a href="ECML_PKDD" title="ECML PKDD">ECML PKDD</a></li>
<li><a href="Conference_on_Neural_Information_Processing_Systems" title="Conference on Neural Information Processing Systems">NeurIPS</a></li>
<li><a href="International_Conference_on_Machine_Learning" title="International Conference on Machine Learning">ICML</a></li>
<li><a href="International_Conference_on_Learning_Representations" title="International Conference on Learning Representations">ICLR</a></li>
<li><a href="International_Joint_Conference_on_Artificial_Intelligence" title="International Joint Conference on Artificial Intelligence">IJCAI</a></li>
<li><a href="Machine_Learning_(journal)" title="Machine Learning (journal)">ML</a></li>
<li><a href="Journal_of_Machine_Learning_Research" title="Journal of Machine Learning Research">JMLR</a></li></ul></div></div></td>
</tr><tr><td class="sidebar-content">
<div class="sidebar-list mw-collapsible mw-collapsed machine-learning-list-title"><div class="sidebar-list-title" style="border-top:1px solid #aaa; text-align:center;;color: var(--color-base)">Related articles</div><div class="sidebar-list-content mw-collapsible-content hlist">
<ul><li><a href="Glossary_of_artificial_intelligence" title="Glossary of artificial intelligence">Glossary of artificial intelligence</a></li>
<li><a href="List_of_datasets_for_machine-learning_research" title="List of datasets for machine-learning research">List of datasets for machine-learning research</a>
<ul><li><a href="List_of_datasets_in_computer_vision_and_image_processing" title="List of datasets in computer vision and image processing">List of datasets in computer vision and image processing</a></li></ul></li>
<li><a href="Outline_of_machine_learning" title="Outline of machine learning">Outline of machine learning</a></li></ul></div></div></td>
</tr><tr><td class="sidebar-navbar"><style data-mw-deduplicate="TemplateStyles:r1239400231">
/* start https://en.wikipedia.org/ */
.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}
/* end https://en.wikipedia.org/ */
</style></td></tr></tbody></table>
<p>The <b>sample complexity</b> of a <a href="Machine_learning" title="Machine learning">machine learning</a> algorithm represents the number of training-samples that it needs in order to successfully learn a target function.
</p><p>More precisely, the sample complexity is the number of training-samples that we need to supply to the algorithm, so that the function returned by the algorithm is within an arbitrarily small error of the best possible function, with probability arbitrarily close to 1.
</p><p>There are two variants of sample complexity:
</p>
<ul><li>The weak variant fixes a particular input-output distribution;</li>
<li>The strong variant takes the worst-case sample complexity over all input-output distributions.</li></ul>
<p>The <a href="No_free_lunch_theorem" title="No free lunch theorem">No free lunch theorem</a>, discussed below, proves that, in general, the strong sample complexity is infinite, i.e. that there is no algorithm that can learn the globally-optimal target function using a finite number of training samples.
</p><p>However, if we are only interested in a particular class of target functions (e.g., only linear functions) then the sample complexity is finite, and it depends linearly on the <a href="VC_dimension" class="mw-redirect" title="VC dimension">VC dimension</a> on the class of target functions.<sup id="cite_ref-:0_1-0" class="reference"><a href="#cite_note-:0-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>
</p>
<meta property="mw:PageProp/toc">
<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>
<p>Let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>X</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle X}</annotation>
</semantics>
</math></span><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span> be a space which we call the input space, and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>Y</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>
</semantics>
</math></span><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"></span> be a space which we call the output space, and let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Z}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>Z</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle Z}</annotation>
</semantics>
</math></span><img src="./1cc6b75e09a8aa3f04d8584b11db534f88fb56bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.68ex; height:2.176ex;" alt="{\displaystyle Z}" loading="lazy"></span> denote the product <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\times Y}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>X</mi>
<mo>×<!-- × --></mo>
<mi>Y</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle X\times Y}</annotation>
</semantics>
</math></span><img src="./1613c1ff4b6fbfb6c80a8da83e90ad28f0ab3483.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.594ex; height:2.176ex;" alt="{\displaystyle X\times Y}" loading="lazy"></span>. For example, in the setting of binary classification, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>X</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle X}</annotation>
</semantics>
</math></span><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span> is typically a finite-dimensional vector space and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>Y</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>
</semantics>
</math></span><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"></span> is the set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{-1,1\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo fence="false" stretchy="false">{</mo>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo>,</mo>
<mn>1</mn>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \{-1,1\}}</annotation>
</semantics>
</math></span><img src="./c0ffb8c7a09dad8456eee3669ee9a7e462fe3c34.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.492ex; height:2.843ex;" alt="{\displaystyle \{-1,1\}}" loading="lazy"></span>.
</p><p>Fix a hypothesis space <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span> of functions <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h\colon X\to Y}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>h</mi>
<mo>:<!-- : --></mo>
<mi>X</mi>
<mo stretchy="false">→<!-- → --></mo>
<mi>Y</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle h\colon X\to Y}</annotation>
</semantics>
</math></span><img src="./a29ad513ef913b52f2055fd2f761194dd1207d75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.74ex; height:2.176ex;" alt="{\displaystyle h\colon X\to Y}" loading="lazy"></span>. A learning algorithm over <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span> is a computable map from <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Z}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>Z</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle Z}</annotation>
</semantics>
</math></span><img src="./1cc6b75e09a8aa3f04d8584b11db534f88fb56bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.68ex; height:2.176ex;" alt="{\displaystyle Z}" loading="lazy"></span> to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span>. In other words, it is an algorithm that takes as input a finite sequence of training samples and outputs a function from <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>X</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle X}</annotation>
</semantics>
</math></span><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span> to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Y}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>Y</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle Y}</annotation>
</semantics>
</math></span><img src="./961d67d6b454b4df2301ac571808a3538b3a6d3f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.773ex; height:2.009ex;" alt="{\displaystyle Y}" loading="lazy"></span>. Typical learning algorithms include <a href="Empirical_risk_minimization" title="Empirical risk minimization">empirical risk minimization</a>, without or with <a href="Tikhonov_regularization" class="mw-redirect" title="Tikhonov regularization">Tikhonov regularization</a>.
</p><p>Fix a loss function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {L}}\colon Y\times Y\to \mathbb {R} _{\geq 0}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">L</mi>
</mrow>
</mrow>
<mo>:<!-- : --></mo>
<mi>Y</mi>
<mo>×<!-- × --></mo>
<mi>Y</mi>
<mo stretchy="false">→<!-- → --></mo>
<msub>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">R</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo>≥<!-- ≥ --></mo>
<mn>0</mn>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {L}}\colon Y\times Y\to \mathbb {R} _{\geq 0}}</annotation>
</semantics>
</math></span><img src="./ef183714ba1638b99e4cf982b8b815616cb99acb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.65ex; height:2.676ex;" alt="{\displaystyle {\mathcal {L}}\colon Y\times Y\to \mathbb {R} _{\geq 0}}" loading="lazy"></span>, for example, the square loss <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {L}}(y,y')=(y-y')^{2}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">L</mi>
</mrow>
</mrow>
<mo stretchy="false">(</mo>
<mi>y</mi>
<mo>,</mo>
<msup>
<mi>y</mi>
<mo>′</mo>
</msup>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mo stretchy="false">(</mo>
<mi>y</mi>
<mo>−<!-- − --></mo>
<msup>
<mi>y</mi>
<mo>′</mo>
</msup>
<msup>
<mo stretchy="false">)</mo>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {L}}(y,y')=(y-y')^{2}}</annotation>
</semantics>
</math></span><img src="./72ec2472e008f2dae53a2fcd284f8d5c30d67d9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.251ex; height:3.176ex;" alt="{\displaystyle {\mathcal {L}}(y,y')=(y-y')^{2}}" loading="lazy"></span>, where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h(x)=y'}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>h</mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<msup>
<mi>y</mi>
<mo>′</mo>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle h(x)=y'}</annotation>
</semantics>
</math></span><img src="./8f354309fce8695514ec70925940a645f55423d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.422ex; height:3.009ex;" alt="{\displaystyle h(x)=y'}" loading="lazy"></span>. For a given distribution <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>ρ<!-- ρ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \rho }</annotation>
</semantics>
</math></span><img src="./1f7d439671d1289b6a816e6af7a304be40608d64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.202ex; height:2.176ex;" alt="{\displaystyle \rho }" loading="lazy"></span> on <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X\times Y}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>X</mi>
<mo>×<!-- × --></mo>
<mi>Y</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle X\times Y}</annotation>
</semantics>
</math></span><img src="./1613c1ff4b6fbfb6c80a8da83e90ad28f0ab3483.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.594ex; height:2.176ex;" alt="{\displaystyle X\times Y}" loading="lazy"></span>, the <b>expected risk</b> of a hypothesis (a function) <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h\in {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>h</mi>
<mo>∈<!-- ∈ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle h\in {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./9fc935233bd00796f06e499cc016a5e2eb8b903a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.143ex; height:2.176ex;" alt="{\displaystyle h\in {\mathcal {H}}}" loading="lazy"></span> is
</p>
<dl><dd><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {E}}(h):=\mathbb {E} _{\rho }[{\mathcal {L}}(h(x),y)]=\int _{X\times Y}{\mathcal {L}}(h(x),y)\,d\rho (x,y)}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">E</mi>
</mrow>
</mrow>
<mo stretchy="false">(</mo>
<mi>h</mi>
<mo stretchy="false">)</mo>
<mo>:=</mo>
<msub>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">E</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>ρ<!-- ρ --></mi>
</mrow>
</msub>
<mo stretchy="false">[</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">L</mi>
</mrow>
</mrow>
<mo stretchy="false">(</mo>
<mi>h</mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mi>y</mi>
<mo stretchy="false">)</mo>
<mo stretchy="false">]</mo>
<mo>=</mo>
<msub>
<mo>∫<!-- ∫ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>X</mi>
<mo>×<!-- × --></mo>
<mi>Y</mi>
</mrow>
</msub>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">L</mi>
</mrow>
</mrow>
<mo stretchy="false">(</mo>
<mi>h</mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mi>y</mi>
<mo stretchy="false">)</mo>
<mspace width="thinmathspace"></mspace>
<mi>d</mi>
<mi>ρ<!-- ρ --></mi>
<mo stretchy="false">(</mo>
<mi>x</mi>
<mo>,</mo>
<mi>y</mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {E}}(h):=\mathbb {E} _{\rho }[{\mathcal {L}}(h(x),y)]=\int _{X\times Y}{\mathcal {L}}(h(x),y)\,d\rho (x,y)}</annotation>
</semantics>
</math></span><img src="./98594a59eb6e7d6681c3ffded4aff29a40d662d6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:49.368ex; height:5.676ex;" alt="{\displaystyle {\mathcal {E}}(h):=\mathbb {E} _{\rho }[{\mathcal {L}}(h(x),y)]=\int _{X\times Y}{\mathcal {L}}(h(x),y)\,d\rho (x,y)}" loading="lazy"></span></dd></dl>
<p>In our setting, we have <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h={\mathcal {A}}(S_{n})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>h</mi>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">A</mi>
</mrow>
</mrow>
<mo stretchy="false">(</mo>
<msub>
<mi>S</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle h={\mathcal {A}}(S_{n})}</annotation>
</semantics>
</math></span><img src="./e03645401852507fc1c009fcba5044d85e367c48.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.793ex; height:2.843ex;" alt="{\displaystyle h={\mathcal {A}}(S_{n})}" loading="lazy"></span>, where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {A}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">A</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {A}}}</annotation>
</semantics>
</math></span><img src="./280ae03440942ab348c2ca9b8db6b56ffa9618f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.903ex; height:2.343ex;" alt="{\displaystyle {\mathcal {A}}}" loading="lazy"></span> is a learning algorithm and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>S</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo>=</mo>
<mo stretchy="false">(</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>y</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>y</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo stretchy="false">)</mo>
<mo>∼<!-- ∼ --></mo>
<msup>
<mi>ρ<!-- ρ --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}}</annotation>
</semantics>
</math></span><img src="./e4cd4d42503b768a6f223c287a01d9d02487cc4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.418ex; height:2.843ex;" alt="{\displaystyle S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}}" loading="lazy"></span> is a sequence of vectors which are all drawn independently from <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>ρ<!-- ρ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \rho }</annotation>
</semantics>
</math></span><img src="./1f7d439671d1289b6a816e6af7a304be40608d64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.202ex; height:2.176ex;" alt="{\displaystyle \rho }" loading="lazy"></span>. Define the optimal risk<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}={\underset {h\in {\mathcal {H}}}{\inf }}{\mathcal {E}}(h).}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msubsup>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">E</mi>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo>∗<!-- ∗ --></mo>
</mrow>
</msubsup>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<munder>
<mo form="prefix">inf</mo>
<mrow>
<mi>h</mi>
<mo>∈<!-- ∈ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mrow>
</munder>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">E</mi>
</mrow>
</mrow>
<mo stretchy="false">(</mo>
<mi>h</mi>
<mo stretchy="false">)</mo>
<mo>.</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}={\underset {h\in {\mathcal {H}}}{\inf }}{\mathcal {E}}(h).}</annotation>
</semantics>
</math></span></span>Set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{n}={\mathcal {A}}(S_{n})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>h</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">A</mi>
</mrow>
</mrow>
<mo stretchy="false">(</mo>
<msub>
<mi>S</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle h_{n}={\mathcal {A}}(S_{n})}</annotation>
</semantics>
</math></span><img src="./d183a6b86e9428fe63a22492c8b07ace14fa030c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.012ex; height:2.843ex;" alt="{\displaystyle h_{n}={\mathcal {A}}(S_{n})}" loading="lazy"></span>, for each <a href="Sample_size" class="mw-redirect" title="Sample size">sample size</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>. <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>h</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle h_{n}}</annotation>
</semantics>
</math></span><img src="./dc869ca124a4bbb264113f1b3b40d78e09c055be.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.557ex; height:2.509ex;" alt="{\displaystyle h_{n}}" loading="lazy"></span> is a <a href="Random_variable" title="Random variable">random variable</a> and depends on the random variable <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>S</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle S_{n}}</annotation>
</semantics>
</math></span><img src="./9f049ac28d4ac8097b625f9d71c1f22b2ebd1bc4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.643ex; height:2.509ex;" alt="{\displaystyle S_{n}}" loading="lazy"></span>, which is drawn from the distribution <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho ^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msup>
<mi>ρ<!-- ρ --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \rho ^{n}}</annotation>
</semantics>
</math></span><img src="./66253fd273e924614c16f768c236be4de3e5f687.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.42ex; height:2.843ex;" alt="{\displaystyle \rho ^{n}}" loading="lazy"></span>. The algorithm <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {A}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">A</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {A}}}</annotation>
</semantics>
</math></span><img src="./280ae03440942ab348c2ca9b8db6b56ffa9618f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.903ex; height:2.343ex;" alt="{\displaystyle {\mathcal {A}}}" loading="lazy"></span> is called <b>consistent</b> if <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {E}}(h_{n})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">E</mi>
</mrow>
</mrow>
<mo stretchy="false">(</mo>
<msub>
<mi>h</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {E}}(h_{n})}</annotation>
</semantics>
</math></span><img src="./596f9e02b2a96f805d6b46e096c5cdf442deab4a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.678ex; height:2.843ex;" alt="{\displaystyle {\mathcal {E}}(h_{n})}" loading="lazy"></span> probabilistically converges to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msubsup>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">E</mi>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo>∗<!-- ∗ --></mo>
</mrow>
</msubsup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}}</annotation>
</semantics>
</math></span><img src="./3fcc0693c8d90b67503000f857d0bfe1a41b9759.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.848ex; height:2.843ex;" alt="{\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}}" loading="lazy"></span>. In other words, for all <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon ,\delta >0}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>ϵ<!-- ϵ --></mi>
<mo>,</mo>
<mi>δ<!-- δ --></mi>
<mo>></mo>
<mn>0</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \epsilon ,\delta >0}</annotation>
</semantics>
</math></span><img src="./fe275792c3e14300c529497c66171c3d5e51192d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.288ex; height:2.676ex;" alt="{\displaystyle \epsilon ,\delta >0}" loading="lazy"></span>, there exists a positive integer <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N}</annotation>
</semantics>
</math></span><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span>, such that, for all sample sizes <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\geq N}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
<mo>≥<!-- ≥ --></mo>
<mi>N</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n\geq N}</annotation>
</semantics>
</math></span><img src="./4b67a4f8e2ce89617f08316bfdcc6f33887b5629.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.557ex; height:2.343ex;" alt="{\displaystyle n\geq N}" loading="lazy"></span>, we have
</p><p><span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]<\delta .}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<munder>
<mo movablelimits="true" form="prefix">Pr</mo>
<mrow class="MJX-TeXAtom-ORD">
<msup>
<mi>ρ<!-- ρ --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mrow>
</munder>
<mo stretchy="false">[</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">E</mi>
</mrow>
</mrow>
<mo stretchy="false">(</mo>
<msub>
<mi>h</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>−<!-- − --></mo>
<msubsup>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">E</mi>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo>∗<!-- ∗ --></mo>
</mrow>
</msubsup>
<mo>≥<!-- ≥ --></mo>
<mi>ε<!-- ε --></mi>
<mo stretchy="false">]</mo>
<mo><</mo>
<mi>δ<!-- δ --></mi>
<mo>.</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]<\delta .}</annotation>
</semantics>
</math></span></span>The <b>sample complexity</b> of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {A}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">A</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {A}}}</annotation>
</semantics>
</math></span><img src="./280ae03440942ab348c2ca9b8db6b56ffa9618f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.903ex; height:2.343ex;" alt="{\displaystyle {\mathcal {A}}}" loading="lazy"></span> is then the minimum <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N}</annotation>
</semantics>
</math></span><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span> for which this holds, as a function of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho ,\epsilon }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>ρ<!-- ρ --></mi>
<mo>,</mo>
<mi>ϵ<!-- ϵ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \rho ,\epsilon }</annotation>
</semantics>
</math></span><img src="./6b47f70c8e2468216b45c97dbf46037292a20b50.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.18ex; height:2.176ex;" alt="{\displaystyle \rho ,\epsilon }" loading="lazy"></span>, and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>δ<!-- δ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>
</semantics>
</math></span><img src="./c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy"></span>. We write the sample complexity as <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N(\rho ,\epsilon ,\delta )}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
<mo stretchy="false">(</mo>
<mi>ρ<!-- ρ --></mi>
<mo>,</mo>
<mi>ϵ<!-- ϵ --></mi>
<mo>,</mo>
<mi>δ<!-- δ --></mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N(\rho ,\epsilon ,\delta )}</annotation>
</semantics>
</math></span><img src="./1b9eabec9c25bff887fb3a003661228d8bad1aee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.136ex; height:2.843ex;" alt="{\displaystyle N(\rho ,\epsilon ,\delta )}" loading="lazy"></span> to emphasize that this value of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N}</annotation>
</semantics>
</math></span><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span> depends on <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho ,\epsilon }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>ρ<!-- ρ --></mi>
<mo>,</mo>
<mi>ϵ<!-- ϵ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \rho ,\epsilon }</annotation>
</semantics>
</math></span><img src="./6b47f70c8e2468216b45c97dbf46037292a20b50.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.18ex; height:2.176ex;" alt="{\displaystyle \rho ,\epsilon }" loading="lazy"></span>, and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>δ<!-- δ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>
</semantics>
</math></span><img src="./c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy"></span>. If <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {A}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">A</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {A}}}</annotation>
</semantics>
</math></span><img src="./280ae03440942ab348c2ca9b8db6b56ffa9618f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.903ex; height:2.343ex;" alt="{\displaystyle {\mathcal {A}}}" loading="lazy"></span> is <b>not consistent</b>, then we set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N(\rho ,\epsilon ,\delta )=\infty }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
<mo stretchy="false">(</mo>
<mi>ρ<!-- ρ --></mi>
<mo>,</mo>
<mi>ϵ<!-- ϵ --></mi>
<mo>,</mo>
<mi>δ<!-- δ --></mi>
<mo stretchy="false">)</mo>
<mo>=</mo>
<mi mathvariant="normal">∞<!-- ∞ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N(\rho ,\epsilon ,\delta )=\infty }</annotation>
</semantics>
</math></span><img src="./7f21d8d7ccf1be5b37a82f29dcc03808d0d2176c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.558ex; height:2.843ex;" alt="{\displaystyle N(\rho ,\epsilon ,\delta )=\infty }" loading="lazy"></span>. If there exists an algorithm for which <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N(\rho ,\epsilon ,\delta )}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
<mo stretchy="false">(</mo>
<mi>ρ<!-- ρ --></mi>
<mo>,</mo>
<mi>ϵ<!-- ϵ --></mi>
<mo>,</mo>
<mi>δ<!-- δ --></mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N(\rho ,\epsilon ,\delta )}</annotation>
</semantics>
</math></span><img src="./1b9eabec9c25bff887fb3a003661228d8bad1aee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.136ex; height:2.843ex;" alt="{\displaystyle N(\rho ,\epsilon ,\delta )}" loading="lazy"></span> is finite, then we say that the hypothesis space <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span> is <b>learnable</b>.
</p><p>In others words, the sample complexity <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N(\rho ,\epsilon ,\delta )}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
<mo stretchy="false">(</mo>
<mi>ρ<!-- ρ --></mi>
<mo>,</mo>
<mi>ϵ<!-- ϵ --></mi>
<mo>,</mo>
<mi>δ<!-- δ --></mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N(\rho ,\epsilon ,\delta )}</annotation>
</semantics>
</math></span><img src="./1b9eabec9c25bff887fb3a003661228d8bad1aee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.136ex; height:2.843ex;" alt="{\displaystyle N(\rho ,\epsilon ,\delta )}" loading="lazy"></span> defines the rate of consistency of the algorithm: given a desired accuracy <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>ϵ<!-- ϵ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation>
</semantics>
</math></span><img src="./c3837cad72483d97bcdde49c85d3b7b859fb3fd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }" loading="lazy"></span> and confidence <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \delta }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>δ<!-- δ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \delta }</annotation>
</semantics>
</math></span><img src="./c5321cfa797202b3e1f8620663ff43c4660ea03a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:2.343ex;" alt="{\displaystyle \delta }" loading="lazy"></span>, one needs to sample <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N(\rho ,\epsilon ,\delta )}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
<mo stretchy="false">(</mo>
<mi>ρ<!-- ρ --></mi>
<mo>,</mo>
<mi>ϵ<!-- ϵ --></mi>
<mo>,</mo>
<mi>δ<!-- δ --></mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N(\rho ,\epsilon ,\delta )}</annotation>
</semantics>
</math></span><img src="./1b9eabec9c25bff887fb3a003661228d8bad1aee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.136ex; height:2.843ex;" alt="{\displaystyle N(\rho ,\epsilon ,\delta )}" loading="lazy"></span> data points to guarantee that the risk of the output function is within <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>ϵ<!-- ϵ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \epsilon }</annotation>
</semantics>
</math></span><img src="./c3837cad72483d97bcdde49c85d3b7b859fb3fd2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.944ex; height:1.676ex;" alt="{\displaystyle \epsilon }" loading="lazy"></span> of the best possible, with probability at least <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-\delta }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>1</mn>
<mo>−<!-- − --></mo>
<mi>δ<!-- δ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 1-\delta }</annotation>
</semantics>
</math></span><img src="./e7fc18b68a939b8f9eb465e354a64164a1202901.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.052ex; height:2.509ex;" alt="{\displaystyle 1-\delta }" loading="lazy"></span> .<sup id="cite_ref-Rosasco_2-0" class="reference"><a href="#cite_note-Rosasco-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>
</p><p>In <a href="Probably_approximately_correct_learning" title="Probably approximately correct learning">probably approximately correct (PAC) learning</a>, one is concerned with whether the sample complexity is <i>polynomial</i>, that is, whether <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N(\rho ,\epsilon ,\delta )}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
<mo stretchy="false">(</mo>
<mi>ρ<!-- ρ --></mi>
<mo>,</mo>
<mi>ϵ<!-- ϵ --></mi>
<mo>,</mo>
<mi>δ<!-- δ --></mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N(\rho ,\epsilon ,\delta )}</annotation>
</semantics>
</math></span><img src="./1b9eabec9c25bff887fb3a003661228d8bad1aee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.136ex; height:2.843ex;" alt="{\displaystyle N(\rho ,\epsilon ,\delta )}" loading="lazy"></span> is bounded by a polynomial in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/\epsilon }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>1</mn>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mi>ϵ<!-- ϵ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 1/\epsilon }</annotation>
</semantics>
</math></span><img src="./656e71e33c17e6e344d005ee2fadfed2d4f2a7b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.269ex; height:2.843ex;" alt="{\displaystyle 1/\epsilon }" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1/\delta }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>1</mn>
<mrow class="MJX-TeXAtom-ORD">
<mo>/</mo>
</mrow>
<mi>δ<!-- δ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 1/\delta }</annotation>
</semantics>
</math></span><img src="./6c5382fc7faa85b5bbd8e06331aa061c3daa9b91.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.374ex; height:2.843ex;" alt="{\displaystyle 1/\delta }" loading="lazy"></span>. If <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N(\rho ,\epsilon ,\delta )}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
<mo stretchy="false">(</mo>
<mi>ρ<!-- ρ --></mi>
<mo>,</mo>
<mi>ϵ<!-- ϵ --></mi>
<mo>,</mo>
<mi>δ<!-- δ --></mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N(\rho ,\epsilon ,\delta )}</annotation>
</semantics>
</math></span><img src="./1b9eabec9c25bff887fb3a003661228d8bad1aee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.136ex; height:2.843ex;" alt="{\displaystyle N(\rho ,\epsilon ,\delta )}" loading="lazy"></span> is polynomial for some learning algorithm, then one says that the hypothesis space <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span> is <b>PAC-learnable</b>. This is a stronger notion than being learnable.
</p>
<div class="mw-heading mw-heading2"><h2 id="Unrestricted_hypothesis_space:_infinite_sample_complexity">Unrestricted hypothesis space: infinite sample complexity</h2></div>
<p>
One can ask whether there exists a learning algorithm so that the sample complexity is finite in the strong sense, that is, there is a bound on the number of samples needed so that the algorithm can learn any distribution over the input-output space with a specified target error. More formally, one asks whether there exists a learning algorithm <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {A}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">A</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {A}}}</annotation>
</semantics>
</math></span><img src="./280ae03440942ab348c2ca9b8db6b56ffa9618f8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.903ex; height:2.343ex;" alt="{\displaystyle {\mathcal {A}}}" loading="lazy"></span>, such that, for all <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \epsilon ,\delta >0}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>ϵ<!-- ϵ --></mi>
<mo>,</mo>
<mi>δ<!-- δ --></mi>
<mo>></mo>
<mn>0</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \epsilon ,\delta >0}</annotation>
</semantics>
</math></span><img src="./fe275792c3e14300c529497c66171c3d5e51192d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.288ex; height:2.676ex;" alt="{\displaystyle \epsilon ,\delta >0}" loading="lazy"></span>, there exists a positive integer <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N}</annotation>
</semantics>
</math></span><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"></span> such that for all <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\geq N}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
<mo>≥<!-- ≥ --></mo>
<mi>N</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n\geq N}</annotation>
</semantics>
</math></span><img src="./4b67a4f8e2ce89617f08316bfdcc6f33887b5629.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:6.557ex; height:2.343ex;" alt="{\displaystyle n\geq N}" loading="lazy"></span>, we have
</p><p><span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right)<\delta ,}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<munder>
<mo movablelimits="true" form="prefix">sup</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>ρ<!-- ρ --></mi>
</mrow>
</munder>
<mrow>
<mo>(</mo>
<mrow>
<munder>
<mo movablelimits="true" form="prefix">Pr</mo>
<mrow class="MJX-TeXAtom-ORD">
<msup>
<mi>ρ<!-- ρ --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mrow>
</munder>
<mo stretchy="false">[</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">E</mi>
</mrow>
</mrow>
<mo stretchy="false">(</mo>
<msub>
<mi>h</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>−<!-- − --></mo>
<msubsup>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">E</mi>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo>∗<!-- ∗ --></mo>
</mrow>
</msubsup>
<mo>≥<!-- ≥ --></mo>
<mi>ε<!-- ε --></mi>
<mo stretchy="false">]</mo>
</mrow>
<mo>)</mo>
</mrow>
<mo><</mo>
<mi>δ<!-- δ --></mi>
<mo>,</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right)<\delta ,}</annotation>
</semantics>
</math></span></span>
where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h_{n}={\mathcal {A}}(S_{n})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>h</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo>=</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">A</mi>
</mrow>
</mrow>
<mo stretchy="false">(</mo>
<msub>
<mi>S</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle h_{n}={\mathcal {A}}(S_{n})}</annotation>
</semantics>
</math></span><img src="./d183a6b86e9428fe63a22492c8b07ace14fa030c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.012ex; height:2.843ex;" alt="{\displaystyle h_{n}={\mathcal {A}}(S_{n})}" loading="lazy"></span>, with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>S</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo>=</mo>
<mo stretchy="false">(</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>y</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mo>…<!-- … --></mo>
<mo>,</mo>
<mo stretchy="false">(</mo>
<msub>
<mi>x</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mi>y</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo stretchy="false">)</mo>
<mo>∼<!-- ∼ --></mo>
<msup>
<mi>ρ<!-- ρ --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}}</annotation>
</semantics>
</math></span><img src="./e4cd4d42503b768a6f223c287a01d9d02487cc4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:33.418ex; height:2.843ex;" alt="{\displaystyle S_{n}=((x_{1},y_{1}),\ldots ,(x_{n},y_{n}))\sim \rho ^{n}}" loading="lazy"></span> as above. The <a href="No_free_lunch_in_search_and_optimization" title="No free lunch in search and optimization">No Free Lunch Theorem</a> says that without restrictions on the hypothesis space <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span>, this is not the case, i.e., there always exist "bad" distributions for which the sample complexity is arbitrarily large.<sup id="cite_ref-:0_1-1" class="reference"><a href="#cite_note-:0-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>
</p><p>Thus, in order to make statements about the rate of convergence of the quantity
<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right),}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<munder>
<mo movablelimits="true" form="prefix">sup</mo>
<mrow class="MJX-TeXAtom-ORD">
<mi>ρ<!-- ρ --></mi>
</mrow>
</munder>
<mrow>
<mo>(</mo>
<mrow>
<munder>
<mo movablelimits="true" form="prefix">Pr</mo>
<mrow class="MJX-TeXAtom-ORD">
<msup>
<mi>ρ<!-- ρ --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msup>
</mrow>
</munder>
<mo stretchy="false">[</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">E</mi>
</mrow>
</mrow>
<mo stretchy="false">(</mo>
<msub>
<mi>h</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
<mo stretchy="false">)</mo>
<mo>−<!-- − --></mo>
<msubsup>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">E</mi>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo>∗<!-- ∗ --></mo>
</mrow>
</msubsup>
<mo>≥<!-- ≥ --></mo>
<mi>ε<!-- ε --></mi>
<mo stretchy="false">]</mo>
</mrow>
<mo>)</mo>
</mrow>
<mo>,</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \sup _{\rho }\left(\Pr _{\rho ^{n}}[{\mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right),}</annotation>
</semantics>
</math></span></span>
one must either
</p>
<ul><li>constrain the space of probability distributions <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \rho }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>ρ<!-- ρ --></mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \rho }</annotation>
</semantics>
</math></span><img src="./1f7d439671d1289b6a816e6af7a304be40608d64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:1.202ex; height:2.176ex;" alt="{\displaystyle \rho }" loading="lazy"></span>, e.g. via a parametric approach, or</li>
<li>constrain the space of hypotheses <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span>, as in distribution-free approaches.</li></ul>
<div class="mw-heading mw-heading2"><h2 id="Restricted_hypothesis_space:_finite_sample-complexity">Restricted hypothesis space: finite sample-complexity</h2></div>
<p>The latter approach leads to concepts such as <a href="VC_dimension" class="mw-redirect" title="VC dimension">VC dimension</a> and <a href="Rademacher_complexity" title="Rademacher complexity">Rademacher complexity</a> which control the complexity of the space <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span>. A smaller hypothesis space introduces more bias into the inference process, meaning that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msubsup>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">E</mi>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mo>∗<!-- ∗ --></mo>
</mrow>
</msubsup>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}}</annotation>
</semantics>
</math></span><img src="./3fcc0693c8d90b67503000f857d0bfe1a41b9759.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.848ex; height:2.843ex;" alt="{\displaystyle {\mathcal {E}}_{\mathcal {H}}^{*}}" loading="lazy"></span> may be greater than the best possible risk in a larger space. However, by restricting the complexity of the hypothesis space it becomes possible for an algorithm to produce more uniformly consistent functions. This trade-off leads to the concept of <a href="Regularization_(mathematics)" title="Regularization (mathematics)">regularization</a>.<sup id="cite_ref-Rosasco_2-1" class="reference"><a href="#cite_note-Rosasco-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>
</p><p>It is a theorem from <a href="Vapnik%E2%80%93Chervonenkis_theory" title="Vapnik–Chervonenkis theory">VC theory</a> that the following three statements are equivalent for a hypothesis space <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span>:
</p>
<ol><li><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span> is PAC-learnable.</li>
<li>The VC dimension of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span> is finite.</li>
<li><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span> is a uniform <a href="Glivenko-Cantelli_class" class="mw-redirect" title="Glivenko-Cantelli class">Glivenko-Cantelli class</a>.</li></ol>
<p>This gives a way to prove that certain hypothesis spaces are PAC learnable, and by extension, learnable.
</p>
<div class="mw-heading mw-heading3"><h3 id="An_example_of_a_PAC-learnable_hypothesis_space">An example of a PAC-learnable hypothesis space</h3></div>
<p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X=\mathbb {R} ^{d},Y=\{-1,1\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>X</mi>
<mo>=</mo>
<msup>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">R</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>d</mi>
</mrow>
</msup>
<mo>,</mo>
<mi>Y</mi>
<mo>=</mo>
<mo fence="false" stretchy="false">{</mo>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo>,</mo>
<mn>1</mn>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle X=\mathbb {R} ^{d},Y=\{-1,1\}}</annotation>
</semantics>
</math></span><img src="./850e8ea84fd75f94e7836f387de2752a8aec6f53.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:21.246ex; height:3.176ex;" alt="{\displaystyle X=\mathbb {R} ^{d},Y=\{-1,1\}}" loading="lazy"></span>, and let <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span> be the space of affine functions on <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle X}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>X</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle X}</annotation>
</semantics>
</math></span><img src="./68baa052181f707c662844a465bfeeb135e82bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.98ex; height:2.176ex;" alt="{\displaystyle X}" loading="lazy"></span>, that is, functions of the form <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\mapsto \langle w,x\rangle +b}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>x</mi>
<mo stretchy="false">↦<!-- ↦ --></mo>
<mo fence="false" stretchy="false">⟨<!-- ⟨ --></mo>
<mi>w</mi>
<mo>,</mo>
<mi>x</mi>
<mo fence="false" stretchy="false">⟩<!-- ⟩ --></mo>
<mo>+</mo>
<mi>b</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle x\mapsto \langle w,x\rangle +b}</annotation>
</semantics>
</math></span><img src="./5a23a0796c1833060e31288e1e788eb3ee3dc7ff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.619ex; height:2.843ex;" alt="{\displaystyle x\mapsto \langle w,x\rangle +b}" loading="lazy"></span> for some <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle w\in \mathbb {R} ^{d},b\in \mathbb {R} }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>w</mi>
<mo>∈<!-- ∈ --></mo>
<msup>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">R</mi>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mi>d</mi>
</mrow>
</msup>
<mo>,</mo>
<mi>b</mi>
<mo>∈<!-- ∈ --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mi mathvariant="double-struck">R</mi>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle w\in \mathbb {R} ^{d},b\in \mathbb {R} }</annotation>
</semantics>
</math></span><img src="./f11c2f98c7b82376a8f11876dc7631fd10b99657.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.825ex; height:3.009ex;" alt="{\displaystyle w\in \mathbb {R} ^{d},b\in \mathbb {R} }" loading="lazy"></span>. This is the linear classification with offset learning problem. Now, four coplanar points in a square cannot be shattered by any affine function, since no affine function can be positive on two diagonally opposite vertices and negative on the remaining two. Thus, the VC dimension of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span> is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d+1}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>d</mi>
<mo>+</mo>
<mn>1</mn>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle d+1}</annotation>
</semantics>
</math></span><img src="./056e0c06c828dbe71a0f9021b2828ff176a3d337.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.219ex; height:2.343ex;" alt="{\displaystyle d+1}" loading="lazy"></span>, so it is finite. It follows by the above characterization of PAC-learnable classes that <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span> is PAC-learnable, and by extension, learnable.
</p>
<div class="mw-heading mw-heading3"><h3 id="Sample-complexity_bounds">Sample-complexity bounds</h3></div>
<p>
Suppose <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span> is a class of binary functions (functions to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{0,1\}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo fence="false" stretchy="false">{</mo>
<mn>0</mn>
<mo>,</mo>
<mn>1</mn>
<mo fence="false" stretchy="false">}</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle \{0,1\}}</annotation>
</semantics>
</math></span><img src="./28de5781698336d21c9c560fb1cbb3fb406923eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.684ex; height:2.843ex;" alt="{\displaystyle \{0,1\}}" loading="lazy"></span>). Then, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span> is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\epsilon ,\delta )}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">(</mo>
<mi>ϵ<!-- ϵ --></mi>
<mo>,</mo>
<mi>δ<!-- δ --></mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle (\epsilon ,\delta )}</annotation>
</semantics>
</math></span><img src="./7c713274f5fc4c0c8a1a8e561c72314c0c5f0db6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.836ex; height:2.843ex;" alt="{\displaystyle (\epsilon ,\delta )}" loading="lazy"></span>-PAC-learnable with a sample of size:
<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>
<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=O{\bigg (}{\frac {VC({\mathcal {H}})+\ln {1 \over \delta }}{\epsilon }}{\bigg )}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
<mo>=</mo>
<mi>O</mi>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mo maxsize="2.047em" minsize="2.047em">(</mo>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mi>V</mi>
<mi>C</mi>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>ln</mi>
<mo><!-- --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>1</mn>
<mi>δ<!-- δ --></mi>
</mfrac>
</mrow>
</mrow>
<mi>ϵ<!-- ϵ --></mi>
</mfrac>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mo maxsize="2.047em" minsize="2.047em">)</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N=O{\bigg (}{\frac {VC({\mathcal {H}})+\ln {1 \over \delta }}{\epsilon }}{\bigg )}}</annotation>
</semantics>
</math></span></span>
where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle VC({\mathcal {H}})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>V</mi>
<mi>C</mi>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle VC({\mathcal {H}})}</annotation>
</semantics>
</math></span><img src="./efbf514b8fbba672236fbb76ee2bdd433e8745e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.327ex; height:2.843ex;" alt="{\displaystyle VC({\mathcal {H}})}" loading="lazy"></span> is the <a href="VC_dimension" class="mw-redirect" title="VC dimension">VC dimension</a> of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span>.
Moreover, any <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\epsilon ,\delta )}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">(</mo>
<mi>ϵ<!-- ϵ --></mi>
<mo>,</mo>
<mi>δ<!-- δ --></mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle (\epsilon ,\delta )}</annotation>
</semantics>
</math></span><img src="./7c713274f5fc4c0c8a1a8e561c72314c0c5f0db6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.836ex; height:2.843ex;" alt="{\displaystyle (\epsilon ,\delta )}" loading="lazy"></span>-PAC-learning algorithm for <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span> must have sample-complexity:<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>
<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=\Omega {\bigg (}{\frac {VC({\mathcal {H}})+\ln {1 \over \delta }}{\epsilon }}{\bigg )}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
<mo>=</mo>
<mi mathvariant="normal">Ω<!-- Ω --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mo maxsize="2.047em" minsize="2.047em">(</mo>
</mrow>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mi>V</mi>
<mi>C</mi>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
<mo stretchy="false">)</mo>
<mo>+</mo>
<mi>ln</mi>
<mo><!-- --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>1</mn>
<mi>δ<!-- δ --></mi>
</mfrac>
</mrow>
</mrow>
<mi>ϵ<!-- ϵ --></mi>
</mfrac>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mo maxsize="2.047em" minsize="2.047em">)</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N=\Omega {\bigg (}{\frac {VC({\mathcal {H}})+\ln {1 \over \delta }}{\epsilon }}{\bigg )}}</annotation>
</semantics>
</math></span></span>
Thus, the sample-complexity is a linear function of the <a href="VC_dimension" class="mw-redirect" title="VC dimension">VC dimension</a> of the hypothesis space.
</p><p>Suppose <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span> is a class of real-valued functions with range in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle [0,T]}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">[</mo>
<mn>0</mn>
<mo>,</mo>
<mi>T</mi>
<mo stretchy="false">]</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle [0,T]}</annotation>
</semantics>
</math></span><img src="./35ccef2d3dc751e081375d51c111709d8a1d7ac6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.126ex; height:2.843ex;" alt="{\displaystyle [0,T]}" loading="lazy"></span>. Then, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span> is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (\epsilon ,\delta )}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mo stretchy="false">(</mo>
<mi>ϵ<!-- ϵ --></mi>
<mo>,</mo>
<mi>δ<!-- δ --></mi>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle (\epsilon ,\delta )}</annotation>
</semantics>
</math></span><img src="./7c713274f5fc4c0c8a1a8e561c72314c0c5f0db6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.836ex; height:2.843ex;" alt="{\displaystyle (\epsilon ,\delta )}" loading="lazy"></span>-PAC-learnable with a sample of size:
<sup id="cite_ref-mr15_5-0" class="reference"><a href="#cite_note-mr15-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>
<span class="mwe-math-element mwe-math-element-block"><span class="mwe-math-mathml-display mwe-math-mathml-a11y" style="display: none;"><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=O{\bigg (}T^{2}{\frac {PD({\mathcal {H}})\ln {T \over \epsilon }+\ln {1 \over \delta }}{\epsilon ^{2}}}{\bigg )}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>N</mi>
<mo>=</mo>
<mi>O</mi>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mo maxsize="2.047em" minsize="2.047em">(</mo>
</mrow>
</mrow>
<msup>
<mi>T</mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mrow>
<mi>P</mi>
<mi>D</mi>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
<mo stretchy="false">)</mo>
<mi>ln</mi>
<mo><!-- --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mi>T</mi>
<mi>ϵ<!-- ϵ --></mi>
</mfrac>
</mrow>
<mo>+</mo>
<mi>ln</mi>
<mo><!-- --></mo>
<mrow class="MJX-TeXAtom-ORD">
<mfrac>
<mn>1</mn>
<mi>δ<!-- δ --></mi>
</mfrac>
</mrow>
</mrow>
<msup>
<mi>ϵ<!-- ϵ --></mi>
<mrow class="MJX-TeXAtom-ORD">
<mn>2</mn>
</mrow>
</msup>
</mfrac>
</mrow>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mo maxsize="2.047em" minsize="2.047em">)</mo>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle N=O{\bigg (}T^{2}{\frac {PD({\mathcal {H}})\ln {T \over \epsilon }+\ln {1 \over \delta }}{\epsilon ^{2}}}{\bigg )}}</annotation>
</semantics>
</math></span></span>
where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle PD({\mathcal {H}})}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>P</mi>
<mi>D</mi>
<mo stretchy="false">(</mo>
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
<mo stretchy="false">)</mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle PD({\mathcal {H}})}</annotation>
</semantics>
</math></span><img src="./3faabb579a5a8b3c0cc95185622d9fdddc5c2e9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.443ex; height:2.843ex;" alt="{\displaystyle PD({\mathcal {H}})}" loading="lazy"></span> is <a href="VC_dimension" class="mw-redirect" title="VC dimension">Pollard's pseudo-dimension</a> of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mrow class="MJX-TeXAtom-ORD">
<mrow class="MJX-TeXAtom-ORD">
<mi class="MJX-tex-caligraphic" mathvariant="script">H</mi>
</mrow>
</mrow>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>
</semantics>
</math></span><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy"></span>.
</p>
<div class="mw-heading mw-heading2"><h2 id="Other_settings">Other settings</h2></div>
<p>In addition to the supervised learning setting, sample complexity is relevant to <a href="Semi-supervised_learning" class="mw-redirect" title="Semi-supervised learning">semi-supervised learning</a> problems including <a href="Active_learning_(machine_learning)" title="Active learning (machine learning)">active learning</a>,<sup id="cite_ref-Balcan_7-0" class="reference"><a href="#cite_note-Balcan-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> where the algorithm can ask for labels to specifically chosen inputs in order to reduce the cost of obtaining many labels. The concept of sample complexity also shows up in <a href="Reinforcement_learning" title="Reinforcement learning">reinforcement learning</a>,<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup> <a href="Online_machine_learning" title="Online machine learning">online learning</a>, and unsupervised algorithms, e.g. for <a href="Dictionary_learning" class="mw-redirect" title="Dictionary learning">dictionary learning</a>.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="Efficiency_in_robotics">Efficiency in robotics</h2></div>
<p>A high sample complexity means that many calculations are needed for running a <a href="Monte_Carlo_tree_search" title="Monte Carlo tree search">Monte Carlo tree search</a>.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> It is equivalent to a <a href="Model-free_(reinforcement_learning)" title="Model-free (reinforcement learning)">model-free</a> brute force search in the state space. In contrast, a high-efficiency algorithm has a low sample complexity.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> Possible techniques for reducing the sample complexity are <a href="Metric_learning" class="mw-redirect" title="Metric learning">metric learning</a><sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> and model-based reinforcement learning.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2></div>
<ul><li><a href="Active_learning_(machine_learning)" title="Active learning (machine learning)">Active learning (machine learning)</a></li></ul>
<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>
<style data-mw-deduplicate="TemplateStyles:r1239543626">
/* start https://en.wikipedia.org/ */
.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}
/* end https://en.wikipedia.org/ */
</style><div class="reflist">
<div class="mw-references-wrap mw-references-columns"><ol class="references">
<li id="cite_note-:0-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_1-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">
/* start https://en.wikipedia.org/ */
.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}
/* end https://en.wikipedia.org/ */
</style><cite id="CITEREFVapnik1998" class="citation cs2">Vapnik, Vladimir (1998), <i>Statistical Learning Theory</i>, New York: Wiley.</cite></span>
</li>
<li id="cite_note-Rosasco-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-Rosasco_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-Rosasco_2-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFRosasco2014" class="citation cs2">Rosasco, Lorenzo (2014), <i>Consistency, Learnability, and Regularization</i>, Lecture Notes for MIT Course 9.520.</cite></span>
</li>
<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFSteve_Hanneke2016" class="citation journal cs1">Steve Hanneke (2016). <a rel="nofollow" class="external text" href="https://www.jmlr.org/papers/v17/15-389.html">"The optimal sample complexity of PAC learning"</a>. <i>J. Mach. Learn. Res</i>. <b>17</b> (1): <span class="nowrap">1319–</span>1333. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1507.00473">1507.00473</a></span>.</cite></span>
</li>
<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFEhrenfeuchtHausslerKearnsValiant1989" class="citation journal cs1">Ehrenfeucht, Andrzej; Haussler, David; Kearns, Michael; Valiant, Leslie (1989). <a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0890-5401%2889%2990002-3">"A general lower bound on the number of examples needed for learning"</a>. <i>Information and Computation</i>. <b>82</b> (3): 247. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0890-5401%2889%2990002-3">10.1016/0890-5401(89)90002-3</a></span>.</cite></span>
</li>
<li id="cite_note-mr15-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-mr15_5-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFAnthonyBartlett2009" class="citation book cs1">Anthony, Martin; Bartlett, Peter L. (2009). <i>Neural Network Learning: Theoretical Foundations</i>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780521118620</bdi>.</cite></span>
</li>
<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFMorgensternRoughgarden2015" class="citation conference cs1"><a href="Jamie_Morgenstern" title="Jamie Morgenstern">Morgenstern, Jamie</a>; Roughgarden, Tim (2015). <a rel="nofollow" class="external text" href="http://papers.nips.cc/paper/5766-on-the-pseudo-dimension-of-nearly-optimal-auctions"><i>On the Pseudo-Dimension of Nearly Optimal Auctions</i></a>. NIPS. Curran Associates. pp. <span class="nowrap">136–</span>144. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1506.03684">1506.03684</a></span>.</cite></span>
</li>
<li id="cite_note-Balcan-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-Balcan_7-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFBalcanHannekeWortman_Vaughan2010" class="citation journal cs1"><a href="Maria-Florina_Balcan" title="Maria-Florina Balcan">Balcan, Maria-Florina</a>; Hanneke, Steve; Wortman Vaughan, Jennifer (2010). <a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10994-010-5174-y">"The true sample complexity of active learning"</a>. <i>Machine Learning</i>. <b>80</b> (<span class="nowrap">2–</span>3): <span class="nowrap">111–</span>139. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10994-010-5174-y">10.1007/s10994-010-5174-y</a></span>.</cite></span>
</li>
<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFKakade2003" class="citation cs2">Kakade, Sham (2003), <a rel="nofollow" class="external text" href="http://www.ias.tu-darmstadt.de/uploads/Research/NIPS2006/SK.pdf"><i>On the Sample Complexity of Reinforcement Learning</i></a> <span class="cs1-format">(PDF)</span>, PhD Thesis, University College London: Gatsby Computational Neuroscience Unit.</cite></span>
</li>
<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFVainsencherMannorBruckstein2011" class="citation journal cs1">Vainsencher, Daniel; Mannor, Shie; Bruckstein, Alfred (2011). <a rel="nofollow" class="external text" href="http://www.jmlr.org/papers/volume12/vainsencher11a/vainsencher11a.pdf">"The Sample Complexity of Dictionary Learning"</a> <span class="cs1-format">(PDF)</span>. <i>Journal of Machine Learning Research</i>. <b>12</b>: <span class="nowrap">3259–</span>3281.</cite></span>
</li>
<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite id="CITEREFKaufmann,_Emilie_and_Koolen,_Wouter_M2017" class="citation conference cs1">Kaufmann, Emilie and Koolen, Wouter M (2017). <i>Monte-carlo tree search by best arm identification</i>. Advances in Neural Information Processing Systems. pp. <span class="nowrap">4897–</span>4906.</cite><span class="cs1-maint citation-comment"><code class="cs1-code">{{cite conference}}</code>: CS1 maint: multiple names: authors list (link)</span></span>
</li>
<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text"><cite id="CITEREFFidelman,_Peggy_and_Stone,_Peter2006" class="citation conference cs1">Fidelman, Peggy and Stone, Peter (2006). <i>The chin pinch: A case study in skill learning on a legged robot</i>. Robot Soccer World Cup. Springer. pp. <span class="nowrap">59–</span>71.</cite><span class="cs1-maint citation-comment"><code class="cs1-code">{{cite conference}}</code>: CS1 maint: multiple names: authors list (link)</span></span>
</li>
<li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><cite id="CITEREFVerma,_Nakul_and_Branson,_Kristin2015" class="citation conference cs1">Verma, Nakul and Branson, Kristin (2015). <i>Sample complexity of learning mahalanobis distance metrics</i>. Advances in neural information processing systems. pp. <span class="nowrap">2584–</span>2592.</cite><span class="cs1-maint citation-comment"><code class="cs1-code">{{cite conference}}</code>: CS1 maint: multiple names: authors list (link)</span></span>
</li>
<li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><cite id="CITEREFKurutach,_Thanard_and_Clavera,_Ignasi_and_Duan,_Yan_and_Tamar,_Aviv_and_Abbeel,_Pieter2018" class="citation arxiv cs1">Kurutach, Thanard and Clavera, Ignasi and Duan, Yan and Tamar, Aviv and Abbeel, Pieter (2018). "Model-ensemble trust-region policy optimization". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1802.10592">1802.10592</a></span> [<a rel="nofollow" class="external text" href="https://arxiv.org/archive/cs.LG">cs.LG</a>].</cite><span class="cs1-maint citation-comment"><code class="cs1-code">{{cite arXiv}}</code>: CS1 maint: multiple names: authors list (link)</span></span>
</li>
</ol></div></div></div><!--htdig_noindex--><div><div class="zim-footer">
This article is issued from <a class="external text" title="Last edited on 2025-06-25" href="https://en.wikipedia.org/wiki/?title=Sample_complexity&oldid=1297240263">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
</body></html>